package dynamicprogramming;

import devide.Main;

/**
 * @Author: LDeng
 * @Date: 2021-04-23 13:58
 */
public class MaxSubArray {
    public static void main(String[] args) {
        System.out.println(maxSubArray1(new int[]{4,2,5,6,-8,7,-33,4}));
        System.out.println("===========");
        System.out.println(maxSubArray2(new int[]{4,2,5,6,-8,7,-33,4}));
    }

    static int maxSubArray1(int[] nums){
        if(nums==null ||nums.length==0) return 0;
        //dp数组存放以nums[i]结尾的最大连续子序列的和
        int[] dp=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        System.out.println("dp[0]=>"+dp[0]);
        for (int i = 1; i < dp.length; i++) {
            if(dp[i-1]<=0){
                dp[i]=nums[i];
            }else{
                dp[i]=dp[i-1]+nums[i];
            }
            max=Math.max(dp[i],max);
            System.out.println("dp["+i+"]=>"+dp[i]);
        }
        return max;
    }


    //优化空间复杂度
    static int maxSubArray2(int[] nums){
        if(nums==null ||nums.length==0) return 0;
        //dp数组存放以nums[i]结尾的最大连续子序列的和
        int dp=nums[0];
        int max=dp;
        System.out.println("dp[0]=>"+dp);
        for (int i = 1; i < nums.length; i++) {
            int prev=dp; //i=1=> 就是这个dp[0]
            if(dp<=0){
                dp=nums[i];
            }else{
                dp=dp+nums[i];
            }
            max=Math.max(dp,max);
            System.out.println("dp["+i+"]=>"+dp);
        }
        return max;
    }
}
